package com.lfg.leetcode.leetcode0;


public class No55CanJump {

    public static void main(String[] args) {
        boolean ret = jump(new int[]{3,2,1,0,4});
        System.out.println(ret);
    }

    public static boolean canJump2(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int[] step = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int num = nums[i] + i;
            if (num >= nums.length - 1 || nums[num] != 0) {
                step[i] = nums[i];
            }
        }
        int index = step[0];
        for (int i = 0; index < nums.length && i < nums.length; i++) {
            if (step[index] == 0 && nums[index] != 0) {
                index++;
            } else {
                index += step[index];
            }
        }
        if (index >= nums.length - 1) {
            return true;
        }
        return false;
    }

    public static boolean canJump(int[] nums) {
        int n = nums.length, reach = 0;
        for (int i = 0; i < n; ++i) {
            if (i > reach || reach >= n - 1) break;
            reach = Math.max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }


    public static boolean jump(int[] nums) {
        if (nums.length == 0) {
            return true;
        }
        int endIndex = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            endIndex = Math.max(endIndex, i + nums[i]);
            if (endIndex <= i) {
                return false;
            }

            if (endIndex > nums.length) {
                return true;
            }
        }
        return true;
    }
}

